Sufficient Conditions for Maximally Edge-connected and Super-edge-connected Digraphs Depending on the Size

Let D be a finite and simple digraph with vertex set V (D). The minimum degree δ of a digraph D is defined as the minimum value of its out-degrees and its in-degrees. If D is a digraph with minimum degree δ and edge-connectivity λ, then λ ≤ δ. A digraph is maximally edge-connected if λ=δ. A digraph is called super-edge-connected if every minimum edge-cut consists of edges incident to or from a vertex of minimum degree. In this note we show that a digraph is maximally edge-connected or super-edge-connected if the number of arcs is large enough.     

The circular chromatic numbers of planar digraphs

The circular chromatic number is a refinement of the chromatic number of a graph. It has been established in [3,6,7] that there exists planar graphs with circular chromatic number r if and only if r is a rational in the set {1} ∪ [2,4]. Recently, Mohar, in [1,2] has extended the concept of the circular chromatic number to digraphs and it is interesting to ask what the corresponding result is for digraphs. In this article, we shall prove the new result that there exist planar digraphs with circular chromatic number r if and only if r is a rational in the interval [1,4]. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 14–26, 2007     

On nice and injective-nice tournaments

One way of defining an oriented colouring of a directed graph $\overrightarrow{G}$ is as a homomorphism from $\overrightarrow{G}$ to a target directed graph $\overrightarrow{H}$, and an injective oriented colouring of $\overrightarrow{G}$ can be defined as a homomorphism from $\overrightarrow{G}$ to a target directed graph $\overrightarrow{H}$ such that no two in-neighbours of a vertex of $\overrightarrow{G}$ have the same image. Oriented colourings may be constructed using target directed graphs that are nice, as defined by Hell et al. (2001). We extend the work of Hell et al. by considering target graphs that are tournaments, characterizing nice tournaments, and proving that every nice tournament on $n$ vertices is $k$-nice for some $k\le n+2$. We also give a characterization of tournaments that are nice but not injective-nice.     

Recolouring reflexive digraphs

Given digraphs $G$ and $H$, the colouring graph $\mathbf{Col}(G,H)$ has as its vertices all homomorphism of $G$ to $H$. There is an arc $?\to {?}^{\prime }$ between two homomorphisms if they differ on exactly one vertex $v$, and if $v$ has a loop we also require $?\left(v\right)\to {?}^{\prime }\left(v\right)$. The recolouring problem asks if there is a path in $\mathbf{Col}(G,H)$ between given homomorphisms $?$ and $\psi$. We examine this problem in the case where $G$ is a digraph and $H$ is a reflexive, digraph cycle.We show that for a reflexive digraph cycle $H$ and a reflexive digraph $G$, the problem of determining whether there is a path between two maps in $\mathbf{Col}(G,H)$ can be solved in time polynomial in $G$. When $G$ is not reflexive, we show the same except for certain digraph 4-cycles $H$.     

Connectivity of a general class of inhomogeneous random digraphs

We study a family of directed random graphs whose arcs are sampled independently of each other, and are present in the graph with a probability that depends on the attributes of the vertices involved. In particular, this family of models includes as special cases the directed versions of the Erd?s‐Rényi model, graphs with given expected degrees, the generalized random graph, and the Poissonian random graph. We establish a phase transition for the existence of a giant strongly connected component and provide some other basic properties, including the limiting joint distribution of the degrees and the mean number of arcs. In particular, we show that by choosing the joint distribution of the vertex attributes according to a multivariate regularly varying distribution, one can obtain scale‐free graphs with arbitrary in‐degree/out‐degree dependence.     

SC-Hamiltonian graphs and digraphs: New necessary conditions and their impacts

A graph G on n vertices is said to be separable cost constant Hamiltonian (SC-Hamiltonian) if and only if G is Hamiltonian and for any cost matrix C=(c_(i,j)) associated with G where all tours have the same cost, there exist vectors a=(a₁,…,a_n) and b=(b₁,…,b_n) such that . In this paper we show that for symmetric digraphs strong Hamiltonicity is a necessary condition for SC-Hamiltonicity. As a surprising consequence, we prove that the symmetric digraph obtained from an undirected SC-Hamiltonian graph by edge duplication need not be SC-Hamiltonian. This settles a conjecture of Kabadi and Punnen. We then show that an undirected graph on an even number of nodes having an edge that appears in every Hamiltonian cycle cannot be SC-Hamiltonian. Using this we establish that multiple subdivision of an edge need not preserve SC-Hamiltonicity, disproving a previous claim. Further, we identify other necessary conditions for SC-Hamiltonicity and obtain new classes of SC-Hamiltonian graphs.     

Automorphisms of endomorphism semigroups of reflexive digraphs

A reflexive digraph is a pair (X, ρ), where X is an arbitrary set and ρ is a reflexive binary relation on X. Let End (X, ρ) be the semigroup of endomorphisms of (X, ρ). We determine the group of automorphisms of End (X, ρ) for: digraphs containing an edge not contained in a cycle, digraphs consisting of arbitrary unions of cycles such that cycles of length ≥2 are pairwise disjoint, and some circulant digraphs (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Counting restricted orientations of random graphs

We count orientations of avoiding certain classes of oriented graphs. In particular, we study , the number of orientations of the binomial random graph in which every copy of is transitive, and , the number of orientations of containing no strongly connected copy of . We give the correct order of growth of and up to polylogarithmic factors; for orientations with no cyclic triangle, this significantly improves a result of Allen, Kohayakawa, Mota, and Parente. We also discuss the problem for a single forbidden oriented graph, and state a number of open problems and conjectures.